1. Field of the Invention
The invention relates to a receiver apparatus for use in packet networks, to a source node apparatus for use in Internet Protocol networks, to methods of processing packets in Internet Protocol networks, and to corresponding software.
2. Background Art
Congestion in packet networks may occur for example at routers where flows converge from different sources. As complicated networks may consist of numerous different end systems (sources and receivers), routers, and links, it is usually impossible to match their capacities perfectly. Accordingly, congestion will occur where more packets are received than can be handled. Various ways of handling congestion are known. At the simplest level, buffering is provided to handle temporary overloads. For longer overloads, flow control mechanisms are provided, to enable downstream elements to cause the source to reduce the rate of sending packets.
If a buffer overflows before the source reduces the flow, then packets will be discarded. The source may eventually detect that these packets have not been acknowledged, and retransmit them. This can make the congestion worse, and lead to complete collapse of the network. On the other hand, if the flow control is made too strong to avoid such a collapse, the throughput of the network may be very low, thus making inefficient use of resources.
Other mechanisms to improve efficiency include admission control, preallocation of buffers, and delay sensitive routing, to avoid congested regions.
Flow control relies on some sort of notification of congestion. This may be implicit or explicit. Congestion can be inferred for example from detecting at the source that packets have been discarded downstream, or detecting delays in the time taken for a packet to arrive. However, with such methods there may be a considerable lag between the congestion occurring, and it being detected. Also, it is possible that the packets were discarded or delayed for reasons other than congestion, e.g. link failure, or erroneous routing. Accordingly, explicit congestion notification mechanisms have been used. One method is described in U.S. Pat. No. 5,377,327 (Jain et al) in the context of a system in which at intermediate nodes, a flow is allocated a share of the capacity. If the allocation is exceeded, a flag is set in each packet. The flags may be counted and if the proportion of packets with the flag set exceeds a threshold, then the flow from the source is adjusted.
Another example is in Frame Relay, a data link layer protocol which has both forward explicit congestion notification (FECN) for notifying the receiver, and backward explicit congestion notification for notifying the source directly. ATM also has an FECN mechanism. The Internet Protocols (IP) also include an FECN and a BECN mechanism. The BECN mechanism is in the form of an Internet Control Message Protocol (ICMP) message called the ICMP Source Quench (ISQ) message. However, it is currently recommended that this message not be used, as it may consume too much bandwidth, and thus contribute to the congestion, and is unfair and ineffective in determining which of multiple flows should be limited.
It has been proposed that ISQs be used in conjunction with random early detection (RED) routers, to enable the rate of sending ISQs to be limited, and reflect how much each flow is contributing to the congestion. However, this has not been adopted, and instead, current practice in TCP/IP (Transport Control Protocol/Internet Protocol) involves using TCP, a transport layer protocol, to determine either lost packets or increases in delays using a timeout mechanism, or determining increases in delays, by timing the acknowledgment sent back by the TCP receiver. This enables the TCP sender to infer congestion and react by reducing its window for that flow, that is, the number of packets it can send towards a given receiver before it must wait for acknowledgments from the receiver.
Floyd discloses a methodology for doing ECN for IP. Floyd suggests the use of RED gateways to detect incipient congestion before the queue overflows. The congestion causing packets are marked on their way to the receiver end system (from the sender end system), with a probability proportional to their bandwidth usage, using the CE (Congestion Experienced) bit in the IP header. When the receiver end system receives the congestion causing packet they inform the sender end system to slow down when ACKing that packet by setting the ECE (Explicit Congestion Echo) bit in the TCP header.
The use of ECN capable gateways for notifying end systems prevents unnecessary packet drops. In the ideal situation where everyone supports ECN at the end system as well as the intermediate nodes, sources are now informed quickly and unambiguously that there is congestion in the network and therefore do not have to rely on extrapolating that condition. Floyd also suggests that with the use of tagging congestion-causing packets, other types of networks that the IP packet traverses (e.g., ATM) can employ their own congestion control algorithms as well as have the ability to mark congestion causing packets.
It is an object of the invention to provide improved methods and apparatus. According to a first aspect of the invention there is provided a receiver apparatus for use in an Internet Protocol network comprising a plurality of nodes, the apparatus comprising:
input means for receiving a packet sent across the network using the Internet Protocol;
packet reading means for determining if the packet has been marked according to the Internet Protocol by any of the nodes through which it passed, to indicate congestion at that node;
a packet flow control parameter generator responsive to the packet reading means, for determining a packet flow control parameter; and
output means for sending a message to the source, to control the flow of packets from the source, according to the packet flow control parameter.
An advantage of enabling the receiver to contribute to the flow control is that it can reduce control loop delays caused by waiting at the source for a number of acknowledgments to arrive. Also, it can improve reliability since it enables the receiver to force a rogue source to slow its flow of packets. A further advantage is that the receiver may be aware of different local information and or conditions to those of the source, or may have a more up to date control algorithm, so overall effectiveness of the flow control may be improved if it is adapted by the receiver.
Preferably, the sending means is arranged to send the packet flow control parameter in the message.
An advantage of this is that the receiver may have more direct control over the flow.
Preferably, the message is an acknowledgment of receipt of the packet.
An advantage of this is that it helps keep the number of packets returned to the source, to a minimum. Furthermore, since many protocols already cater for sending acknowledgments, in many cases it will be easy to adapt them in this way, and there may be no additional bandwidth taken up by the message.
Preferably, the message is an acknowledgment of receipt of the packet, and the output means is arranged to delay the acknowledgment on the basis of the packet flow control parameter.
An advantage of this is that the receiver can enter the control loop with little or no modification to the source if it is already arranged to carry out flow control on the basis of acknowledgments received in a given time period. Hence this may give better backward compatibility.
Preferably the packet flow control parameter generator is arranged to be dependent additionally on whether preceding packets were marked.
This enables the control to be more steady in response to transient congestion for example.
Preferably the packet flow control parameter comprises an offered window size, for indicating to the source node how many packets can be sent before the source should wait for an acknowledgement from the receiver.
An advantage of using this parameter is that existing apparatus is arranged to negotiate window size as part of flow set up, and so can be adapted more easily to this new arrangement.
Preferably the message is an acknowledgment of receipt of the packet, the output means being arranged to send the same packet flow control parameter again in an acknowledgment sent in response to a subsequent packet.
An advantage of this is that it may reduce the risk of flow control being affected by the acknowledgments being delayed or lost in transit.
Preferably the packet flow control parameter generator is operable according to redefinable parameters.
An advantage of this is that the flow control can be updated or tailored more easily.
Preferably the packet flow control parameter generator is operable additionally according to a receiver specific parameter.
This enables different receivers to control the flow to suit their local conditions better.
Another aspect of the invention provides a source node apparatus for use in an Internet Protocol network comprising a plurality of nodes, the apparatus comprising:
a packet sending means for sending a packet using across the Internet Protocol network to one of the nodes acting as a receiving node;
a receiver for receiving from the receiving node a packet flow control parameter sent across the Internet Protocol network; and
a flow controller coupled to the packet sending means for controlling a rate of flow of sending further packets from the sending means to the receiving node on the basis of the packet flow control parameter.
Preferably the receiver is capable of receiving congestion notification messages from other nodes in the path of the packet between the source node and the receiving node, the flow controller being operable to control the rate of flow on the basis of the congestion notification messages received from the other nodes.
Another aspect of the invention provides a method of processing packets in an Internet Protocol network comprising a receiver node, a source node and intermediate nodes, the method comprising the steps of: at the receiver node,
receiving a packet sent across the network using the Internet Protocol;
determining if the packet has been marked by any of the nodes through which it passed, to indicate congestion at that node;
determining a packet flow control parameter on the basis of the determination of a marking; and
sending a message to the source node across the Internet Protocol network, to control the flow of packets from the source node, according to the packet flow control parameter.
Preferably the method further comprises the steps of: at the source node,
receiving the message; and
controlling a rate of flow of sending further packets to the receiving node on the basis of the message.
Preferably the message contains the packet flow control parameter, the controlling step being made on the basis of the parameter.
Preferably the method, further comprises the step of delaying sending the message from the receiver node, on the basis of the flow control parameter, the flow controlling step being made by the source on the basis of the time of arrival of the message.
Preferably the method further comprises the preliminary step of determining if the intermediate nodes are able to send congestion notification messages to the source node, the step of determining the flow control parameter at the receiver being carried out on the basis of whether the intermediate nodes are capable of sending congestion notification messages to the source.
Preferably a method uses an application to transmit data across a network, the application causing the network to use a receiver apparatus as set out above to transmit the data. Another aspect of the invention provides software on a computer readable medium for carrying out the above methods.
Any of the preferred features may be combined, and combined with any aspect of the invention, as would be apparent to a person skilled in the art. Other advantages will be apparent to a person skilled in the art, particularly in relation to prior art other than that mentioned above.
To show, by way of example, how to put the invention into practice, embodiments will now be described in more detail, with reference to the accompanying drawings.